package org.myy.learn.hot.堆;

import lombok.extern.slf4j.Slf4j;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

@Slf4j
public class 前K个高频元素 {
    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums){
            map.put(num, map.getOrDefault(num, 0) + 1); //统计
        }
        //PriorityQueue<int[]> queue = new PriorityQueue<>((a,b) -> a[1] - b[1]);
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparing(a -> a[1]));  //两种都是升序
        map.forEach((key, value) -> {
            if (queue.size() == k){
                if (queue.peek()[1] < value){
                    queue.poll();
                    queue.offer(new int[]{key, value});
                }
            } else {
                queue.offer(new int[]{key, value});
            }
        });
        int[] topK = new int[k];
        for (int i=0; i<k; i++){
            topK[i] = queue.poll()[0];
        }
        return topK;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,1,1,2,2,3};
        int k = 2;
        int[] topK = topKFrequent(nums, k);
        log.info("执行结束，高频元素={}", topK);
    }
}
